package SubjectTree.Three;

import java.util.Arrays;

import Utility.TreeNode;

public class ConstructMaximumBinaryTree {

/**
 * 难度：中等
 * 
 * 654. 最大二叉树
 * 	给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 * 		1.二叉树的根是数组 nums 中的最大元素。
 * 		2.左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 		3.右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 	返回有给定数组 nums 构建的 最大二叉树 。
 * 	
 * 示例 1：
 * 		 6
 * 	   /   \
 * 	  3     5
 * 	  \     /
 * 	   2   0
 * 		\
 * 		 1
 * 	输入：nums = [3,2,1,6,0,5]
 * 	输出：[6,3,5,null,2,0,null,null,1]
 * 	解释：递归调用如下所示：
 * 	- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 * 	    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 * 	        - 空数组，无子节点。
 * 	        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 * 	            - 空数组，无子节点。
 * 	            - 只有一个元素，所以子节点是一个值为 1 的节点。
 * 	    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 * 	        - 只有一个元素，所以子节点是一个值为 0 的节点。
 * 	        - 空数组，无子节点。
 * 	
 * 示例 2：
 * 	 3     
 * 	  \     
 * 	   2   
 * 		\
 * 		 1
 * 	输入：nums = [3,2,1]
 * 	输出：[3,null,2,null,1]
 * 	
 * 提示：
 * 	1 <= nums.length <= 1000
 * 	0 <= nums[i] <= 1000
 * 	nums 中的所有整数 互不相同
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ConstructMaximumBinaryTree cmbt = new ConstructMaximumBinaryTree();
		System.out.println(cmbt.constructMaximumBinaryTree(new int[] {3,2,1,6,0,5}));
	}

	public TreeNode constructMaximumBinaryTree(int[] nums) {
		if(nums.length==0)return null;
		
		int rootValue = Arrays.stream(nums).max().getAsInt();
		TreeNode root = new TreeNode(rootValue);
		
		if(nums.length==1)return root;
		
		int delimiterIndex;
		for(delimiterIndex = 0;delimiterIndex<nums.length;delimiterIndex++) {
			if(nums[delimiterIndex]==rootValue)break;
		}
		
		int[] leftNums = new int[delimiterIndex];
		for(int i=0;i<delimiterIndex;i++) {
			leftNums[i] = nums[i];
		}
		int[] rightNums = new int[nums.length - delimiterIndex - 1];
		for(int i=delimiterIndex+1,j=0;i<nums.length;i++,j++) {
			rightNums[j] = nums[i];
		}
		
		root.left = constructMaximumBinaryTree(leftNums);
		root.right = constructMaximumBinaryTree(rightNums);
		
		return root;
    }
	//方法一：递归
	public TreeNode constructMaximumBinaryTree1(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    public TreeNode construct(int[] nums, int l, int r) {
        if (l == r)
            return null;
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    public int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
}
